package arithmetic1.hufumanCode;
import java.util.*;

/*
    哈夫曼编码:
        解析待解析的字符串的每个字符,统计每个字符出现的次数,将所有次数构建成一颗哈夫曼数树，设每个节点的左路径为0，右路径为1
        得到每个字符的编码，然后在对待解析的字符串用哈夫曼编码进行编码
 */
public class HuffmanCode {

    //统计一个字符串每个字符出现的次数
    public static Map<Character,Integer> statistics(String str){
        Map<Character,Integer> map=new HashMap();
        //逐个扫描字符串
        for (int i = 0; i < str.length(); i++) {
            if(map.containsKey(str.charAt(i))){ //如果集合里面已经包含了该字符
                //将该集合里面的数字加1
                map.put(str.charAt(i),map.get(str.charAt(i))+1);
            }else { //集合里面没有改字符
                //将该字符加入集合。并将value设置为1
                map.put(str.charAt(i),1);
            }
        }
        return map;
    }

    //将map集合构建成哈夫曼树
    public static Node huffmanTree(Map<Character,Integer> map){
        List<Node> nodes=new ArrayList<>();
        //取出map的所有数，封装成节点
        Set<Character> keys = map.keySet();
        for(Character c:keys){
            nodes.add(new Node(map.get(c),c));
        }

        while (nodes.size()>1){ //只要还有两个以上的节点，就一直重复
            //排序
            Collections.sort(nodes);
            //取出两个权值最小的节点
            Node node1=nodes.get(0);
            Node node2=nodes.get(1);
            //生成一个父节点
            Node parent=new Node(node1.value+node2.value);
            //将子节点添加到父节点下面
            parent.leftNode=node1;
            parent.rightNode=node2;
            //删除两个子节点
            nodes.remove(node1);
            nodes.remove(node2);
            //将父节点加入到集合
            nodes.add(parent);
        }
        //返回剩余的一个节点
        return nodes.get(0);
    }

    //将哈夫曼树的叶子节点变成哈夫曼编码,并放入集合,形成编码表
    public static void huffmanCode(Node root,String code,Map<Character,String> map){
        if(root!=null){ //哈夫曼树不为空
            if(root.leftNode==null && root.rightNode==null){    //该节点为叶子节点
                //将编码加入集合
                map.put(root.c,code);
            }
            if(root.leftNode!=null){
                huffmanCode(root.leftNode,code+"0",map);
            }
            if(root.rightNode!=null){
                huffmanCode(root.rightNode,code+"1",map);
            }
        }
    }
    public static void huffmanCode(Node root,Map<Character,String> map){
        huffmanCode(root,"",map);
    }

    //得到编码表
    public static Map<Character,String> codeTable(String str){
        //统计字符串每个字符的次数
        Map<Character,Integer> cNumber = statistics(str);
        //构建成一个哈夫曼树
        Node root=huffmanTree(cNumber);
        //得到编码表
        Map<Character,String> map=new HashMap<>();
        huffmanCode(root,map);
        return map;
    }

    //返回字符串的哈夫曼编码
    public static String coding(String str){
        Map<Character, String> map = codeTable(str);
        //根据编码表算出哈夫曼编码
        String codes="";
        //逐个解析字符串
        for (int i = 0; i < str.length(); i++) {
            String code = map.get(str.charAt(i));
            codes+=code;
        }
        return codes;
    }

    //将哈夫曼编码转换成byte数组(将每8位哈夫曼编码转为10进制数存到byte数组里面)
    public static byte[] codeBytes(String coding){
        //算出byte数组的长度
        int len=coding.length()%8==0?coding.length()/8:coding.length()/8+1;
        byte codeBytes[]=new byte[len];
        String str="";
        //将每8位哈夫曼编码转为10进制数存到byte数组里面
        for (int i=0,index=0;i<coding.length();i+=8,index++){
            if(i+8<coding.length()){
                //str的第一位为符号位
                str=coding.substring(i,i+8);
                codeBytes[index]=(byte)Integer.parseInt(str,2);
            }else {
                str=coding.substring(i);
                codeBytes[index]=(byte)Integer.parseInt(str,2);
            }
        }
        return codeBytes;
    }

    //将一个byte转成一个二进制的字符串,flag为true表示需要补齐高位
    public static String byteToBitString(byte b,boolean flag){
        //将byte转为int
        int temp=b;
        //如果是正数需要补高位
        if(flag){
            temp |= 256; //按位与： 1 0000 0000 | 0000 0001 = 1 0000 0001
        }
        String str=Integer.toBinaryString(temp);    //将int转为二进制补码
        if(flag){
            return str;
        }else {
            return str.substring(str.length()-8);
        }
//        return str.substring(str.length()-8);
    }

    //将哈夫曼编码解码,需要哈夫曼编码和编码表,
    public static String decode(byte[] codeBytes,Map<Character,String> codes){
        //将byte数组转换为哈夫曼编码,如果是最后一个字节，不需要补高位
        StringBuilder stringBuilder=new StringBuilder();
        for(int i=0;i<codeBytes.length;i++){
            byte b=codeBytes[i];
//            boolean flag=(i==codeBytes.length-1);
            stringBuilder.append(byteToBitString(b,false));
        }
        System.out.println(stringBuilder.toString());
        //将编码表转换为两个数组
//        Character cs[]=new Character[codes.size()];
//        String values[]=new String[codes.size()];
//        Set<Character> keys = codes.keySet();
//        int index=0;
//        for(Character key:keys){
//            //将key存到cs中
//            cs[index]=key;
//            //将value存到values中
//            values[index]=codes.get(key);
//            index++;
//        }
       return "";
    }

}

class Node implements Comparable<Node>{
    int value;
    Character c;
    Node leftNode;
    Node rightNode;

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Character c) {
        this.value = value;
        this.c = c;
    }

    @Override
    public String toString() {
        return "Node{}";
    }

    @Override
    public int compareTo(Node o) {
        return this.value-o.value;
    }
}

class Test{
    public static void main(String[] args) {
        //fdknvdfdfl
        String str="fdknvdfdfl";
        System.out.println("哈夫曼编码为:");
        String codes = HuffmanCode.coding(str);
        System.out.println(codes);

        byte[] bytes = HuffmanCode.codeBytes(codes );
        System.out.println("byte数组为:");
        System.out.println(Arrays.toString(bytes));

        System.out.println("解码后为:");
        System.out.println(HuffmanCode.decode(bytes,HuffmanCode.codeTable(str)));

//        byte b=(byte)Integer.parseInt("0001",2);
//        System.out.println(b);
//
//        System.out.println(HuffmanCode.byteToBitString(b,true));
    }

}
